package huawei.od;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 宜居星球改造计划
 * 改造区域为 row * column 的网格，有3个值，宜居区-YES、可改造区-NO、死亡区-NA
 * 每个宜居区能同时在每个太阳日向上下左右四个方向的相邻格子进行扩散
 *
 * 如果可以改造，则返回改造的太阳日天数
 * 如果不可以，则返回-1
 *
 * @author syzsn
 */
public class LivablePlanet {

    public static int[][] directions = {{-1,0},{1,0},{0,1},{0,-1}};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 使用 list string[] 组成二位数组
        List<String[]> matrix = new ArrayList<>();
        while (in.hasNextLine()){
            String line = in.nextLine();
            if("".equals(line)){
                break;
            }else{
                matrix.add(line.split(" "));
            }
        }

        // 行数
        int row = matrix.size();
        // 列数
        int column = matrix.get(0).length;

        // 存放 宜居区 的集合
        List<int[]> yesArea = new ArrayList<>();
        // 非宜居区的数量
        int noCount = 0;
        for(int i=0;i<row;i++){
            for(int j=0;j<column;j++){
                if(matrix.get(i)[j].equals("YES")){
                    yesArea.add(new int[]{i,j});
                } else {
                    noCount++;
                }
            }
        }

        if(yesArea.size() == 0){
            System.out.println(-1);
            return;
        }
        if(yesArea.size() == row * column){
            System.out.println(0);
            return;
        }

        System.out.println(bfs(yesArea, matrix, row, column, noCount));
        return;
    }

    /**
     * 计算太阳日的函数
     */
    private static int bfs(List<int[]> yesArea, List<String[]> matrix, int row, int column, int noCount) {
        int result = 0;

        while (yesArea.size()>0 && noCount>0){
            // 新改造 宜居区 数量
            List<int[]> newYesPos = new ArrayList<>();

            for(int[] pos : yesArea){
                // 上下左右 四次循环
                for(int i=0;i<4;i++){
                    int newX = pos[0] + directions[i][0];
                    int newY = pos[1] + directions[i][1];
                    if(newX >= 0 && newX < column
                            && newY >= 0 && newY < row
                            && "NO".equals(matrix.get(newX)[newY])
                    ){
                        matrix.get(newX)[newY] = "YES";
                        newYesPos.add(new int[] {newX, newY});
                        noCount--;
                    }
                }
            }
            System.out.println(JSON.toJSON(matrix));
            System.out.println(JSON.toJSON(newYesPos));
            System.out.println("-----------------------");
            result++;
            yesArea = newYesPos;
        }

        if(noCount == 0){
            return result;
        }else{
            return -1;
        }
    }
}
